#include "huffmantree.h"
using std::list;
using std::string;

HuffmanTree::HuffmanTree()
{
	if(this->InitHuffmanTree() != OK)
		exit(ERROR);
}

HuffmanTree::HuffmanTree(TElemType data, int weight)
{
	this->root = (HuffmanNode *)malloc(sizeof(HuffmanNode));
	this->root->data = data;
	this->root->weight = weight;
}

HuffmanTree::HuffmanTree(HuffmanTree lchild, HuffmanTree rchild)
{
	this->root = (HuffmanNode *)malloc(sizeof(HuffmanNode));
	this->root->data = '#';
	this->root->weight = lchild.Weight() + rchild.Weight();
	this->root->lchild = lchild.Root();
	this->root->rchild = rchild.Root();
}

Status HuffmanTree::InitHuffmanTree()
{
	this->root = NULL;
	return OK;
}

Status HuffmanTree::DestroyHuffmanTree()
{
	return this->ClearHuffmanTree(this->root);
	this->root = NULL;
}

Status HuffmanTree::CreateHuffmanTree(void (*func)(HuffmanNode *T))
{
	(*func)(this->root);
	return OK;
}

Status HuffmanTree::ClearHuffmanTree(HuffmanNode *T = NULL)
{
	if(T == NULL)
		T = this->root;
	if(T)
	{
		if(T->lchild)
			this->ClearHuffmanTree(T->lchild);
		if(T->rchild)
			this->ClearHuffmanTree(T->rchild);
		free(T);
		return OK;
	}
	else
		return ERROR;
	return OK;
}

bool HuffmanTree::HuffmanTreeEmpty()
{
	return (this->root == NULL);
}

int HuffmanTree::HuffmanTreeDepth(HuffmanNode *T = NULL, bool isroot = true)
{
	int ldep, rdep;
	if(isroot)
		T = this->root;
	if(T == NULL)
		return 0;
	else
	{
		ldep = this->HuffmanTreeDepth(T->lchild, false);
		rdep = this->HuffmanTreeDepth(T->rchild, false);
		return (ldep>rdep?ldep:rdep)+1;
	}
}

HuffmanNode *HuffmanTree::Root()
{
	return this->root;
}

TElemType HuffmanTree::Value(HuffmanNode *e)
{
	return e->data;
}

int HuffmanTree::Weight()
{
	return this->root->weight;
}

Status HuffmanTree::Assign(HuffmanNode *e, TElemType value)
{
	e->data = value;
	return OK;
}

HuffmanNode *HuffmanTree::Parent(HuffmanNode *e)
{
	return e->parent;
}

HuffmanNode *HuffmanTree::LeftChild(HuffmanNode *e)
{
	return e->lchild;
}

HuffmanNode *HuffmanTree::RightChild(HuffmanNode *e)
{
	return e->rchild;
}

HuffmanNode *HuffmanTree::LeftSibling(HuffmanNode *e)
{
	if(e->parent->lchild == e)
		return NULL;
	else
		return e->parent->lchild;
}

HuffmanNode *HuffmanTree::RightSibling(HuffmanNode *e)
{
	if(e->parent->rchild == e)
		return NULL;
	else
		return e->parent->rchild;
}

Status HuffmanTree::InsertChild(HuffmanNode *p, int LR, HuffmanNode *c)
{
	if(this->root == NULL)
	{
		printf("insert in root: %d\n", c->data);
		root = c;
		return OK;
	}
	if(LR == 0)
	{
		if(c == NULL || p->lchild != NULL)
			return ERROR;
		p->lchild = c;
		c->parent = p;
		printf("insert in left child of %d: %d\n", p->data, c->data);
	}
	else
	{
		if(c == NULL || p->rchild != NULL)
			return ERROR;
		p->rchild = c;
		c->parent = p;
		printf("insert in right child of %d: %d\n", p->data, c->data);
	}
	return OK;
}

Status HuffmanTree::DeleteChild(HuffmanNode *p, int LR)
{
	if(LR == 0)
	{
		if(p->lchild)
		{
			this->ClearHuffmanTree(p->lchild);
			p->lchild = NULL;
		}
		return OK;
	}
	else
	{
		if(p->rchild)
		{
			this->ClearHuffmanTree(p->rchild);
			p->rchild = NULL;
		}	
		return OK;
	}
	return ERROR;
}

Status HuffmanTree::PreOrderTraverse(Status (*visit)(TElemType e), HuffmanNode *T = NULL, bool isroot = true)
{
	if(isroot)
		T = this->root;
	if(T == NULL)
		return OK;
	if((*visit)(T->data) == OK)
		if(this->PreOrderTraverse(visit, T->lchild, false) == OK)
			if(this->PreOrderTraverse(visit, T->rchild, false) == OK)
				return OK;
	return ERROR;
}

Status HuffmanTree::InOrderTraverse(Status (*visit)(TElemType e), HuffmanNode *T = NULL, bool isroot = true)
{
	if(isroot)
		T = this->root;
	if(T == NULL)
		return OK;
	if(this->InOrderTraverse(visit, T->lchild, false) == OK)
		if((*visit)(T->data) == OK)
			if(this->InOrderTraverse(visit, T->rchild, false) == OK)
				return OK;
	return ERROR;
}

Status HuffmanTree::PostOrderTraverse(Status (*visit)(TElemType e), HuffmanNode *T = NULL, bool isroot = true)
{
	if(isroot)
		T = this->root;
	if(T == NULL)
		return OK;
	if(this->PostOrderTraverse(visit, T->lchild, false) == OK)
		if(this->PostOrderTraverse(visit, T->rchild, false) == OK)
			if((*visit)(T->data) == OK)
				return OK;
	return ERROR;
}

Status HuffmanTree::LevelOrderTraverse(Status (*visit)(TElemType e))
{
	list<HuffmanNode *> nodeList;
	HuffmanNode *temp;
	Status st;
	if(this->root)
		nodeList.push_back(this->root);
	else
		return ERROR;
	while(!nodeList.empty())
	{
		temp = nodeList.front();
		nodeList.pop_front();
		st = (*visit)(temp->data);
		if(st != OK)
			return ERROR;
		if(temp->lchild)
			nodeList.push_back(temp->lchild);
		if(temp->rchild)
			nodeList.push_back(temp->rchild);
	}
	return OK;
}

void HuffmanTree::Output(HuffmanNode *node = NULL, string code = "")
{
	if(node == NULL)
		node = this->root;
	if(node->data != '#')
		std::cout << node->data << "\t" << code << std::endl;
	else
	{
		this->Output(node->lchild, code+"0");
		this->Output(node->rchild, code+"1");
	}
	return;
}

int HuffmanTree::WeighedLength(HuffmanNode *node = NULL, int length = 0)
{
	if(node == NULL)
		node = this->root;
	if(node -> data != '#')
		return length*(node->weight);
	else
		return (WeighedLength(node->lchild, length+1)) + (WeighedLength(node->rchild, length+1));
}
